package problems.daily.y2021m7;

import java.util.Arrays;

/**
 * @author habitplus
 * @since 2021-07-11 10:06
 */
public class T20210711N1 {
    // 274. H-Index
    // 给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
    //
    // h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 N 篇论文中，
    //            总共有 h 篇论文分别被引用了至少 h 次。
    //            且其余的 N-h 篇论文每篇被引用次数不超过 h 次。
    //
    // 例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。
    //
    // 提示：如果 h 有多种可能的值，h 指数是其中最大的那个。
    // 链接：https://leetcode-cn.com/problems/h-index

    public int hIndex01(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        Arrays.sort(citations);
        int n = citations.length;
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n - i) {
                return n - i;
            }
        }
        return 0;
    }

    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        int n = citations.length;
        int i = 0, j = n - 1;
        int pivot;
        while (i < j) {
            pivot = partition(citations, i, j);
            if (citations[pivot] >= n - pivot) {
                j = pivot;
            } else {
                i = pivot + 1;
            }
        }

        return citations[i] >= n - i ? n - i : n - i - 1;
    }

    private int partition(int[] arr, int left, int right) {
        int pivotKey = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= pivotKey) right--;
            if (left < right) {
                arr[left] = arr[right];
                left++;
            }

            while (left <right && arr[left] < pivotKey) left++;
            if (left < right) {
                arr[right--] = arr[left];
            }
        }
        arr[left] = pivotKey;
        return left;
    }

    public static void main(String[] args) {
        System.out.println(new T20210711N1().hIndex(new int[]{3,0,6,1,5}));
    }
}
